package com.chj.nk.gaojishizhan2020xia.class04.chjtest;

import java.util.Arrays;

public class Code02_SplitArrayLargestSum {

	public static int splitArray1(int[] nums, int m) {
		return process(nums, 0, m);
	}

	public static int process(int[] arr, int index, int part) {
		if (index == arr.length) {
			return 0;
		}
		if (part == 0) {
			return -1;
		}
		int first = 0;
		int min = Integer.MAX_VALUE;
		for (int end = index; arr.length - end >= part; end++) {
			first += arr[end];
			int next = process(arr, end + 1, part - 1);
			if (next != -1) {
				min = Math.min(min, Math.max(first, next));
			}
		}
		return min;
	}

	public static int splitArray2(int[] nums, int M) {
		int N = nums.length;
		int[] help = new int[nums.length + 1];
		for (int i = 0; i < N; i++) {
			help[i + 1] = help[i] + nums[i];
		}
		int[][] dp = new int[M + 1][N];
		for (int i = 0; i < N; i++) {
			dp[1][i] = help[i + 1] - help[0];
		}
		for (int i = 1; i < Math.min(N, M); i++) {
			dp[i + 1][i] = Math.max(dp[i][i - 1], nums[i]);
		}
		for (int i = 2; i < dp.length; i++) {
			for (int j = dp[0].length - 1; j >= i; j--) {
				dp[i][j] = Integer.MAX_VALUE;
				for (int k = 0; k <= j; k++) {
					dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][j - k], help[j + 1] - help[j + 1 - k]));
				}
			}
		}

		return dp[M][N - 1];
	}

	public static int splitArray3(int[] nums, int M) {
		int N = nums.length;
		int[] help = new int[nums.length + 1];
		for (int i = 0; i < N; i++) {
			help[i + 1] = help[i] + nums[i];
		}

		int[][] dp = new int[M + 1][N];
		int[][] best = new int[M + 1][N];
		for (int i = 0; i < N; i++) {
			dp[1][i] = help[i + 1] - help[0];
		}
		for (int i = 1; i < Math.min(N, M); i++) {
			dp[i + 1][i] = Math.max(dp[i][i - 1], nums[i]);
			best[i + 1][i] = i;
		}
		for (int i = 2; i < dp.length; i++) {
			for (int j = dp[0].length - 1; j >= i; j--) {
				dp[i][j] = Integer.MAX_VALUE;
				int left = best[i - 1][j] > 0 ? best[i - 1][j] - 1 : 0;
				int right = j == dp[0].length - 1 ? j : best[i][j + 1];
				for (int k = left+1; k <= right; k++) {
					int curAns = Math.max(dp[i - 1][k - 1], help[j + 1] - help[k]);
					if (dp[i][j] > curAns) {
						dp[i][j] = curAns;
						best[i][j] = k;
					}
				}
			}
		}

		return dp[M][N - 1];
	}

	public static int splitArray4(int[] nums, int M) {
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
		}
		long l = 0;
		long r = sum;
		long ans = 0;
		while (l <= r) {
			long mid = (l + r) / 2;
			long cur = getNeedParts(nums, mid);
			if (cur <= M) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return (int) ans;
	}

	public static int getNeedParts(int[] arr, long aim) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > aim) {
				return Integer.MAX_VALUE;
			}
		}
		int parts = 1;
		int all = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (all + arr[i] > aim) {
				parts++;
				all = arr[i];
			} else {
				all += arr[i];
			}
		}
		return parts;
	}

	// for test
	public static int[] getSortedArray(int len, int range) {
		int[] arr = new int[len];
		for (int i = 0; i != len; i++) {
			arr[i] = (int) (Math.random() * range);
		}
		Arrays.sort(arr);
		return arr;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		// {
		// int[] arr = { 1, 1, 1, 4, 3 };
		// int num = 3;
		// System.out.println(splitArray1(arr, num));
		// System.out.println(splitArray2(arr, num));
		// System.out.println(splitArray3(arr, num));
		// System.out.println(splitArray4(arr, num));
		// }
		// {
		// int[] arr = { 1, 1, 3, 3, 4 };
		// int num = 2;
		// System.out.println(splitArray1(arr, num));
		// System.out.println(splitArray2(arr, num));
		// System.out.println(splitArray3(arr, num));
		// System.out.println(splitArray4(arr, num));
		// }
		{
			int[] arr = { 1, 3, 4, 6, 6 };
			int num = 4;
			System.out.println(splitArray1(arr, num));
			System.out.println(splitArray2(arr, num));
			System.out.println(splitArray3(arr, num));
			System.out.println(splitArray4(arr, num));
		}

		int times = 1000; // test time
		int len = 1000; // test array length
		int range = 2000; // every number in [0,range)
		int p = 50; // post office number
		long time1 = 0; // method1 all run time
		long time2 = 0;// method2 all run time
		long start = 0;
		long end = 0;
		int res1 = 0;
		int res2 = 0;
		int[] arr = null;
		for (int i = 0; i != times; i++) {
			arr = getSortedArray(len, range);
			start = System.currentTimeMillis();
			res1 = splitArray4(arr, p);
			end = System.currentTimeMillis();
			time1 += end - start;
			start = System.currentTimeMillis();
			res2 = splitArray3(arr, p);
			end = System.currentTimeMillis();
			time2 += end - start;
			if (res1 != res2) {
				System.out.println("err");
				printArray(arr);
				break;
			}
			if (i % 10 == 0) {
				System.out.print(". ");
			}
		}
		System.out.println();
		System.out.println("method1 all run time(ms): " + time1);
		System.out.println("method2 all run time(ms): " + time2);

	}
}
